//--------------------------------------------------------------------------------------------------
//                                                   ___  __  __  __  __  __  __  __    __  __  ___ 
// Copyright 2010, Koert van der Veer.              / __)(  )(  )(  \/  )(  )(  )(  )  (  )(  )/ __)
// Licensed under the Apache License,              ( (__  )(__)(  )    (  )(__)(  )(__  )(__)( \__ \
// version 2.0; ("the License")                     \___)(______)(_/\/\_)(______)(____)(______)(___/

// You may not use this file except in compliance with the License.
// You may obtain a copy of the License at 
//     http://www.apache.org/licenses/LICENSE-2.0 
//
// Unless required by applicable law or agreed to in writing, software distributed under the License
// is distributed on an "AS IS" BASIS,  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
// or implied. See the License for the specific language governing permissions and limitations under
// the License. 
//--------------------------------------------------------------------------------------------------
// This file is part of cumulus,  an memory manager implementation in C++.  Details are discussed in
// my blog,  which can be found at http://ondergetekende.nl.  Comments,  suggestions and bug reports
// are welcome. They can be added as comments at the blog. Be advised that in its current form, this
// code is most likely not production ready; it simply hasn't been tested sufficiently. 
//--------------------------------------------------------------------------------------------------
// A generalized singly linked list.
// The templated ListEntry needs to provide one public pointers to itself: Next.
// This members needn't be initialized, but it will change while in the list.
// ------------------------------------------------------------------------------------------------

#pragma once

namespace Cumulus
{
namespace Utils
{


template< typename ListEntry >
class SinglyLinkedList : public NonAssignable
{
private:
	ListEntry* Head;
	INT Count;

public:
	class Iterator
	{
	private:
		// The list to be iterated.
		SinglyLinkedList< ListEntry >* List;

		// Instead of storing the current, the previous pointer is stored instead to allow for deletion
		// and insertion (which require the previous entry.
		// The current entry can easily be derived from the previous entry by taking its next pointer
		ListEntry* Previous;

		// @return	the current Entry in the list, or NULL if at the end of the iteration	
		ListEntry* GetCurrent() const
		{
			// Any use of an iterator constructed with the default constructor is invalid.
			assert( List != NULL ); 

			return Previous == NULL ? 
				List->Head : 
				Previous->Next;
		}

		// Moves to the next item.
		void IterateNext()
		{
			// Any use of an iterator constructed with the default constructor is invalid.
			assert( List != NULL ); 

			if( Previous == NULL )
			{
				// Cant moveNext on an empty list
				assert( List->Head != NULL );

				Previous = List->Head;
			}
			else
			{
				// Can't move past the NULL terminator at the end of the iteration
				assert( Previous->Next != NULL );

				Previous = Previous->Next;
			}
		}

	public:
		Iterator() 
			: List( NULL )
			, Previous( NULL )
		{

		}

		Iterator( SinglyLinkedList<ListEntry>& InList )
			: List( &InList )
			, Previous( NULL )
		{

		}

		/// Copy constructor for the iterator. Warning: having multiple iterators on the same list
		/// is potentially dangerous: if one iterator changes the list, all other iterators are
		/// invalid. Using those iterators will result in undefined behavior.
		Iterator( const Iterator& It )
			: List( It.List )
			, Previous( It.Previous )
		{

		}

		/// Assignment operator fot the iterator. Useful for making a copy. Warning: having 
		/// multiple iterators on the same list is potentially dangerous: if one iterator changes 
		/// the list, all other iterators are invalid. Using those iterators will result in 
		/// undefined behavior.
		Iterator& operator=( const Iterator& Other )
		{
			List = Other.List;
			Previous = Other.Previous;
			return *this;
		}

		/// @return	TRUE if the iterator is past the last element
		bool IsAtEnd()
		{
			// if the iterator was constructed using the default constructor, 
			// it is always 'at end'.
			if( List == NULL )
			{
				return true;
			}

			return (Previous == NULL) ? 
				(List->Head == NULL) :
				Previous->Next == NULL;
		}

		/// Access operator to the current item
		/// @return		A pointer to the current entry, or NULL if the iterator was moved past the
		///				last entry.
		ListEntry* operator ->() const { return GetCurrent(); }

		/// Access operator to the current item
		/// @return		A pointer to the current entry, or NULL if the iterator was moved past the
		///				last entry.
		ListEntry& operator*() const { return *GetCurrent(); }

		/// Access operator to the current item
		/// @return		A pointer to the current entry, or NULL if the iterator was moved past the
		///				last entry.
		operator ListEntry*() const { return GetCurrent(); }

		/// Compares the current entry with some other entry
		/// @param	Other	The 'other' entry. Needn't be an entry in this list.
		/// @return		true if the entries match, false otherwise
		bool operator==( ListEntry* Other ) const { return GetCurrent() == Other; }

		/// Compares the current entry with some other entry
		/// @param	Other	The 'other' entry. Needn't be an entry in this list.
		/// @return		false if the entries match, true otherwise
		bool operator!=( ListEntry* Other ) const { return GetCurrent() != Other; }

		/// Pre-increment operator. Moves the iterator to the next item.
		/// It is illegal to increment an iterator that's already at the end. (see IsAtEnd())
		Iterator& operator++()    { IterateNext(); return *this; }

		/// Post-increment operator. Moves the iterator to the next item.
		/// It is illegal to increment an iterator that's already at the end. (see IsAtEnd())
		Iterator operator++(int) 
		{ 
			Iterator Result( *this );
			IterateNext(); 
			return Result; 
		}

		/// Removes the current entry from the list. After this call, all other iterators for the
		/// same list are invalid, and should not be used anymore.
		ListEntry* Remove()
		{
			// Any use of an iterator constructed with the default constructor is invalid.
			assert( List != NULL ); 

			assert( List->GetCount() > 0 ); // can't remove anything from an empty list.
			assert( !IsAtEnd() ); // Can't remove when we're at the end of the list

			List->Count--;

			if( Previous == NULL )
			{
				// Removing the first list item
				ListEntry* Result = List->Head;
				List->Head = Result->Next;
				return Result;
			}
			else
			{
				ListEntry* Result = Previous->Next;
				Previous->Next = Result->Next;
				return Result;
			}
		}

		/// Adds an entry after the current entry in the list. After this call, all other 
		/// iterators for the same list are invalid, and should not be used anymore. Adding an entry
		/// that is already in a list is illegal and will result in undefined behavior.
		void InsertAfter( ListEntry* NewEntry )
		{
			// Any use of an iterator constructed with the default constructor is invalid.
			assert( List != NULL ); 

			assert( NewEntry != NULL );

			List->Count++;
			ListEntry* Current = GetCurrent();

			// don't support adding entries past the EOF mark
			assert( Current != NULL );

			NewEntry->Next = Current->Next;
			Current->Next = NewEntry;
		}

		/// Adds an entry before the current entry in the list. After this call, all other 
		/// iterators for the same list are invalid, and should not be used anymore. Adding an entry
		/// that is already in a list is illegal and will result in undefined behavior.
		void InsertBefore( ListEntry* NewEntry )
		{
			// Any use of an iterator constructed with the default constructor is invalid.
			assert( List != NULL ); 

			assert( NewEntry != NULL );

			List->Count++;

			if( Previous == NULL )
			{
				// Adding at the start of the list
				NewEntry->Next = List->Head;
				List->Head = NewEntry;
				Previous = NewEntry;
			}
			else
			{
				NewEntry->Next = Previous->Next;
				Previous->Next = NewEntry;
				Previous = NewEntry;
			}
		}

		/// Resets the iterator to the first entry of the list.
		void Reset()
		{
			Previous = NULL;
		}
	};


	SinglyLinkedList()
		: Head( NULL )
		, Count( 0 )
	{}

	/// Returns NULL if the list is empty
	Iterator GetHead( )
	{
		return Iterator( *this );
	}

	INT GetCount() 
	{
		return Count;
	}

};

}
}